home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 October / EnigmA AMIGA RUN 01 (1995)(G.R. Edizioni)(IT)[!][issue 1995-10][Aminet 7].iso / Aminet / dev / gcc / ixemul_src.lha / ixemul-41.0 / network / split.c < prev    next >
C/C++ Source or Header  |  1995-05-18  |  18KB  |  692 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)split.c    5.2 (Berkeley) 2/22/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42. #include <db.h>
  43. #include <stdlib.h>
  44. #include <string.h>
  45. #include "btree.h"
  46.  
  47. /*
  48.  *  _BT_SPLIT -- Split a page into two pages.
  49.  *
  50.  *    Splits are caused by insertions, and propogate up the tree in
  51.  *    the usual way.  The root page is always page 1 in the file on
  52.  *    disk, so root splits are handled specially.  On entry to this
  53.  *    routine, t->bt_curpage is the page to be split.
  54.  *
  55.  *    Parameters:
  56.  *        t -- btree in which to do split.
  57.  *
  58.  *    Returns:
  59.  *        RET_SUCCESS, RET_ERROR.
  60.  *
  61.  *    Side Effects:
  62.  *        Changes the notion of the current page.
  63.  */
  64.  
  65. int
  66. _bt_split(t)
  67.     BTREE_P t;
  68. {
  69.     BTHEADER *h;
  70.     BTHEADER *left, *right;
  71.     pgno_t nextpgno, parent;
  72.     int nbytes, len;
  73.     IDATUM *id;
  74.     DATUM *d;
  75.     char *src;
  76.     IDATUM *new;
  77.     pgno_t oldchain;
  78.     u_char flags;
  79.  
  80.     h = (BTHEADER *) t->bt_curpage;
  81.  
  82.     /* split root page specially, since it must remain page 1 */
  83.     if (h->h_pgno == P_ROOT) {
  84.         return (_bt_splitroot(t));
  85.     }
  86.  
  87.     /*
  88.      *  This is a little complicated.  We go to some trouble to
  89.      *  figure out which of the three possible cases -- in-memory tree,
  90.      *  disk tree (no cache), and disk tree (cache) -- we have, in order
  91.      *  to avoid unnecessary copying.  If we have a disk cache, then we
  92.      *  have to do some extra copying, though, since the cache code
  93.      *  manages buffers externally to this code.
  94.      */
  95.  
  96.     if (ISDISK(t) && ISCACHE(t)) {
  97.         if ((left = (BTHEADER *) malloc((unsigned) t->bt_psize))
  98.             == (BTHEADER *) NULL)
  99.             return (RET_ERROR);
  100.         left->h_pgno = left->h_prevpg = left->h_nextpg = P_NONE;
  101.         left->h_flags = t->bt_curpage->h_flags;
  102.         left->h_lower = (index_t)
  103.               (((char *) &(left->h_linp[0])) - ((char *) left));
  104.         left->h_upper = t->bt_psize;
  105.  
  106.     } else {
  107.         if ((left = _bt_allocpg(t)) == (BTHEADER *) NULL)
  108.             return (RET_ERROR);
  109.     }
  110.     left->h_pgno = h->h_pgno;
  111.  
  112.     if ((right = _bt_allocpg(t)) == (BTHEADER *) NULL)
  113.         return (RET_ERROR);
  114.     right->h_pgno = ++(t->bt_npages);
  115.  
  116.     /* now do the split */
  117.     if (_bt_dopsplit(t, left, right) == RET_ERROR)
  118.         return (RET_ERROR);
  119.  
  120.     right->h_prevpg = left->h_pgno;
  121.     nextpgno = right->h_nextpg = h->h_nextpg;
  122.     left->h_nextpg = right->h_pgno;
  123.     left->h_prevpg = h->h_prevpg;
  124.  
  125.     /* okay, now use the left half of the page as the new page */
  126.     if (ISDISK(t) && ISCACHE(t)) {
  127.         (void) bcopy((char *) left, (char *) t->bt_curpage,
  128.                  (int) t->bt_psize);
  129.         (void) free ((char *) left);
  130.         left = t->bt_curpage;
  131.     } else {
  132.         (void) free((char *) t->bt_curpage);
  133.         t->bt_curpage = left;
  134.     }
  135.  
  136.     /*
  137.      *  Write the new pages out.  We need them to stay where they are
  138.      *  until we're done updating the parent pages.
  139.      */
  140.  
  141.     if (_bt_write(t, left, NORELEASE) == RET_ERROR)
  142.         return (RET_ERROR);
  143.     if (_bt_write(t, right, NORELEASE) == RET_ERROR)
  144.         return (RET_ERROR);
  145.  
  146.     /* update 'prev' pointer of old neighbor of left */
  147.     if (nextpgno != P_NONE) {
  148.         if (_bt_getpage(t, nextpgno) == RET_ERROR)
  149.             return (RET_ERROR);
  150.         h = t->bt_curpage;
  151.         h->h_prevpg = right->h_pgno;
  152.         h->h_flags |= F_DIRTY;
  153.     }
  154.  
  155.     if ((parent = _bt_pop(t)) != P_NONE) {
  156.         if (right->h_flags & F_LEAF) {
  157.             d = (DATUM *) GETDATUM(right, 0);
  158.             len = d->d_ksize;
  159.             if (d->d_flags & D_BIGKEY) {
  160.                 bcopy(&(d->d_bytes[0]),
  161.                       (char *) &oldchain,
  162.                       sizeof(oldchain));
  163.                 if (_bt_markchain(t, oldchain) == RET_ERROR)
  164.                     return (RET_ERROR);
  165.                 src = (char *) &oldchain;
  166.                 flags = D_BIGKEY;
  167.             } else {
  168.                 src = (char *) &(d->d_bytes[0]);
  169.                 flags = 0;
  170.             }
  171.         } else {
  172.             id = (IDATUM *) GETDATUM(right, 0);
  173.             len = id->i_size;
  174.             flags = id->i_flags;
  175.             src = (char *) &(id->i_bytes[0]);
  176.         }
  177.         nbytes = len + (sizeof(IDATUM) - sizeof(char));
  178.         new = (IDATUM *) malloc((unsigned) nbytes);
  179.         if (new == (IDATUM *) NULL)
  180.             return (RET_ERROR);
  181.         new->i_size = len;
  182.         new->i_pgno = right->h_pgno;
  183.         new->i_flags = flags;
  184.         if (len > 0)
  185.             (void) bcopy(src, (char *) &(new->i_bytes[0]), len);
  186.  
  187.         nbytes = LONGALIGN(nbytes) + sizeof(index_t);
  188.         if (_bt_getpage(t, parent) == RET_ERROR)
  189.             return (RET_ERROR);
  190.  
  191.         h = t->bt_curpage;
  192.  
  193.         /*
  194.          *  Split the parent if we need to, then reposition the
  195.          *  tree's current page pointer for the new datum.
  196.          */
  197.         if ((h->h_upper - h->h_lower) < nbytes) {
  198.             if (_bt_split(t) == RET_ERROR)
  199.                 return (RET_ERROR);
  200.             if (_bt_reposition(t, new, parent, right->h_prevpg)
  201.                   == RET_ERROR)
  202.                 return (RET_ERROR);
  203.         }
  204.  
  205.         /* okay, now insert the new idatum */
  206.         if (_bt_inserti(t, new, right->h_prevpg) == RET_ERROR)
  207.             return (RET_ERROR);
  208.     }
  209.  
  210.     /*
  211.      *  Okay, split is done; don't need right page stapled down anymore.
  212.      *  The page we call 'left' above is the new version of the old
  213.      *  (split) page, so we can't release it.
  214.      */
  215.  
  216.     if (_bt_release(t, right) == RET_ERROR)
  217.         return (RET_ERROR);
  218.     if (ISDISK(t) && !ISCACHE(t))
  219.         (void) free((char *) right);
  220.  
  221.     return (RET_SUCCESS);
  222. }
  223.  
  224. /*
  225.  *  _BT_REPOSITION -- Reposition the current page pointer of a btree.
  226.  *
  227.  *    After splitting a node in the tree in order to make room for
  228.  *    an insertion, we need to figure out which page after the split
  229.  *    should get the item we want to insert.  This routine positions
  230.  *    the tree's current page pointer appropriately.
  231.  *
  232.  *    Parameters:
  233.  *        t -- tree to position
  234.  *        new -- the item we want to insert
  235.  *        parent -- parent of the node that we just split
  236.  *        prev -- page number of item directly to the left of
  237.  *            new's position in the tree.
  238.  *
  239.  *    Returns:
  240.  *        RET_SUCCESS, RET_ERROR.
  241.  *
  242.  *    Side Effects:
  243.  *        None.
  244.  */
  245.  
  246. int
  247. _bt_reposition(t, new, parent, prev)
  248.     BTREE_P t;
  249.     IDATUM *new;
  250.     pgno_t parent;
  251.     pgno_t prev;
  252. {
  253.     index_t i, next;
  254.     IDATUM *idx;
  255.  
  256.     if (parent == P_ROOT) {
  257.  
  258.         /*
  259.          *  If we just split the root page, then there are guaranteed
  260.          *  to be exactly two IDATUMs on it.  Look at both of them
  261.          *  to see if they point to the page that we want.
  262.          */
  263.  
  264.         if (_bt_getpage(t, parent) == RET_ERROR)
  265.             return (RET_ERROR);
  266.  
  267.         next = NEXTINDEX(t->bt_curpage);
  268.         for (i = 0; i < next; i++) {
  269.             idx = (IDATUM *) GETDATUM(t->bt_curpage, i);
  270.             if (_bt_getpage(t, idx->i_pgno) == RET_ERROR)
  271.                 return (RET_ERROR);
  272.             if (_bt_isonpage(t, new, prev) == RET_SUCCESS)
  273.                 return (RET_SUCCESS);
  274.             if (_bt_getpage(t, parent) == RET_ERROR)
  275.                 return (RET_ERROR);
  276.         }
  277.     } else {
  278.  
  279.         /*
  280.          *  Get the parent page -- which is where the new item would
  281.          *  have gone -- and figure out whether the new item now goes
  282.          *  on the parent, or the page immediately to the right of
  283.          *  the parent.
  284.          */
  285.  
  286.         if (_bt_getpage(t, parent) == RET_ERROR)
  287.             return (RET_ERROR);
  288.         if (_bt_isonpage(t, new, prev) == RET_SUCCESS)
  289.             return (RET_SUCCESS);
  290.         if (_bt_getpage(t, t->bt_curpage->h_nextpg) == RET_ERROR)
  291.             return (RET_ERROR);
  292.         if (_bt_isonpage(t, new, prev) == RET_SUCCESS)
  293.             return (RET_SUCCESS);
  294.     }
  295.     return (RET_ERROR);
  296. }
  297.  
  298. /*
  299.  *  _BT_ISONPAGE -- Is the IDATUM for a given page number on the current page?
  300.  *
  301.  *    This routine is used by _bt_reposition to decide whether the current
  302.  *    page is the correct one on which to insert a new item.
  303.  *
  304.  *    Parameters:
  305.  *        t -- tree to check
  306.  *        new -- the item that will be inserted (used for binary search)
  307.  *        prev -- page number of page whose IDATUM is immediately to
  308.  *            the left of new's position in the tree.
  309.  *
  310.  *    Returns:
  311.  *        RET_SUCCESS, RET_ERROR (corresponding to TRUE, FALSE).
  312.  */
  313.  
  314. int
  315. _bt_isonpage(t, new, prev)
  316.     BTREE_P t;
  317.     IDATUM *new;
  318.     pgno_t prev;
  319. {
  320.     BTHEADER *h = (BTHEADER *) t->bt_curpage;
  321.     index_t i, next;
  322.     IDATUM *idx;
  323.  
  324.     i = _bt_binsrch(t, &(new->i_bytes[0]));
  325.     while (i != 0 && _bt_cmp(t, &(new->i_bytes[0]), i) == 0)
  326.         --i;
  327.     next = NEXTINDEX(h);
  328.     idx = (IDATUM *) GETDATUM(h, i);
  329.     while (i < next && idx->i_pgno != prev) {
  330.         i++;
  331.         idx = (IDATUM *) GETDATUM(h, i);
  332.     }
  333.     if (idx->i_pgno == prev)
  334.         return (RET_SUCCESS);
  335.     else
  336.         return (RET_ERROR);
  337. }
  338.  
  339. /*
  340.  *  _BT_SPLITROOT -- Split the root of a btree.
  341.  *
  342.  *    The root page for a btree is always page one.  This means that in
  343.  *    order to split the root, we need to do extra work.
  344.  *
  345.  *    Parameters:
  346.  *        t -- tree to split
  347.  *
  348.  *    Returns:
  349.  *        RET_SUCCESS, RET_ERROR.
  350.  *
  351.  *    Side Effects:
  352.  *        Splits root upward in the usual way, adding two new pages
  353.  *        to the tree (rather than just one, as in usual splits).
  354.  */
  355.  
  356. int
  357. _bt_splitroot(t)
  358.     BTREE_P t;
  359. {
  360.     BTHEADER *h = t->bt_curpage;
  361.     BTHEADER *left, *right;
  362.     IDATUM *id;
  363.     BTHEADER *where_h;
  364.     char *src, *dest;
  365.     int len, nbytes;
  366.     u_long was_leaf;
  367.     pgno_t oldchain;
  368.     u_char flags;
  369.  
  370.     /* get two new pages for the split */
  371.     if ((left = _bt_allocpg(t)) == (BTHEADER *) NULL)
  372.         return (RET_ERROR);
  373.     left->h_pgno = ++(t->bt_npages);
  374.     if ((right = _bt_allocpg(t)) == (BTHEADER *) NULL)
  375.         return (RET_ERROR);
  376.     right->h_pgno = ++(t->bt_npages);
  377.  
  378.     /* do the split */
  379.     if (_bt_dopsplit(t, left, right) == RET_ERROR)
  380.         return (RET_ERROR);
  381.  
  382.     /* connect the new pages correctly */
  383.     right->h_prevpg = left->h_pgno;
  384.     left->h_nextpg = right->h_pgno;
  385.  
  386.     /*
  387.      *  Write the child pages out now.  We need them to remain
  388.      *  where they are until we finish updating parent pages,
  389.      *  however.
  390.      */
  391.  
  392.     if (_bt_write(t, left, NORELEASE) == RET_ERROR)
  393.         return (RET_ERROR);
  394.     if (_bt_write(t, right, NORELEASE) == RET_ERROR)
  395.         return (RET_ERROR);
  396.  
  397.     /* now change the root page into an internal page */
  398.     was_leaf = (h->h_flags & F_LEAF);
  399.     h->h_flags &= ~F_LEAF;
  400.     h->h_lower = (index_t) (((char *) (&(h->h_linp[0]))) - ((char *) h));
  401.     h->h_upper = (index_t) t->bt_psize;
  402.     (void) bzero((char *) &(h->h_linp[0]), (int) (h->h_upper - h->h_lower));
  403.  
  404.     /* put two new keys on root page */
  405.     where_h = left;
  406.     while (where_h) {
  407.         DATUM *data;
  408.         IDATUM *idata;
  409.  
  410.         if (was_leaf) {
  411.             data = (DATUM *) GETDATUM(where_h, 0);
  412.  
  413.             if (where_h == left) {
  414.                 len = 0;    /* first key in tree is null */
  415.             } else {
  416.                 if (data->d_flags & D_BIGKEY) {
  417.                     bcopy(&(data->d_bytes[0]),
  418.                           (char *) &oldchain,
  419.                           sizeof(oldchain));
  420.                     if (_bt_markchain(t, oldchain) == RET_ERROR)
  421.                         return (RET_ERROR);
  422.                     src = (char *) &oldchain;
  423.                     flags = D_BIGKEY;
  424.                 } else {
  425.                     src = (char *) &(data->d_bytes[0]);
  426.                     flags = 0;
  427.                 }
  428.                 len = data->d_ksize;
  429.             }
  430.         } else {
  431.             idata = (IDATUM *) GETDATUM(where_h, 0);
  432.             len = idata->i_size;
  433.             flags = idata->i_flags;
  434.             src = &(idata->i_bytes[0]);
  435.         }
  436.         dest = ((char *) h) + h->h_upper;
  437.         nbytes = len + (sizeof (IDATUM) - sizeof(char));
  438.         dest -= LONGALIGN(nbytes);
  439.         id = (IDATUM *) dest;
  440.         id->i_size = len;
  441.         id->i_pgno = where_h->h_pgno;
  442.         id->i_flags = flags;
  443.         if (len > 0)
  444.             (void) bcopy((char *) src, (char *) &(id->i_bytes[0]), len);
  445.         dest -= ((int) h);
  446.         h->h_linp[NEXTINDEX(h)] = (index_t) dest;
  447.         h->h_upper = (index_t) dest;
  448.         h->h_lower += sizeof(index_t);
  449.  
  450.         /* next page */
  451.         if (where_h == left)
  452.             where_h = right;
  453.         else
  454.             where_h = (BTHEADER *) NULL;
  455.     }
  456.  
  457.     if (_bt_release(t, left) == RET_ERROR)
  458.         return (RET_ERROR);
  459.     if (_bt_release(t, right) == RET_ERROR)
  460.         return (RET_ERROR);
  461.  
  462.     /*
  463.      *  That's it, split is done.  If we're doing a non-cached disk
  464.      *  btree, we can free up the pages we allocated, as they're on
  465.      *  disk, now.
  466.      */
  467.  
  468.     if (ISDISK(t) && !ISCACHE(t)) {
  469.         (void) free ((char *) left);
  470.         (void) free ((char *) right);
  471.     }
  472.  
  473.     h->h_flags |= F_DIRTY;
  474.  
  475.     return (RET_SUCCESS);
  476. }
  477.  
  478. /*
  479.  *  _BT_DOPSPLIT -- Do the work of splitting a page
  480.  *
  481.  *    This routine takes two page pointers and splits the data on the
  482.  *    current page of the btree between them.
  483.  *
  484.  *    We do a lot of work here to handle duplicate keys on a page; we
  485.  *    have to place these keys carefully to guarantee that later searches
  486.  *    will find them correctly.  See comments in the code below for details.
  487.  *
  488.  *    Parameters:
  489.  *        t -- tree to split
  490.  *        left -- pointer to page to get left half of the data
  491.  *        right -- pointer to page to get right half of the data
  492.  *
  493.  *    Returns:
  494.  *        None.
  495.  */
  496.  
  497. int
  498. _bt_dopsplit(t, left, right)
  499.     BTREE_P t;
  500.     BTHEADER *left;
  501.     BTHEADER *right;
  502. {
  503.     BTHEADER *h = t->bt_curpage;
  504.     size_t psize;
  505.     char *where;
  506.     BTHEADER *where_h;
  507.     index_t where_i;
  508.     int nbytes, dsize, fixedsize, freespc;
  509.     index_t i;
  510.     index_t save_lower, save_upper, save_i;
  511.     index_t switch_i;
  512.     char *save_key;
  513.     DATUM *d;
  514.     CURSOR *c;
  515.     index_t top;
  516.     int free_save;
  517.     pgno_t chain;
  518.     int ignore;
  519.  
  520.     /*
  521.      *  Our strategy is to put half the bytes on each page.  We figure
  522.      *  out how many bytes we have total, and then move items until
  523.      *  the last item moved put at least 50% of the data on the left
  524.      *  page.
  525.      */
  526.     save_key = (char *) NULL;
  527.     psize = (int) t->bt_psize;
  528.     where = ((char *) left) + psize;
  529.     where_h = left;
  530.     where_i = 0;
  531.     nbytes = psize - (int) ((char *) &(h->h_linp[0]) - ((char *) h));
  532.     freespc = nbytes;
  533.  
  534.     top = NEXTINDEX(h);
  535.     if (h->h_flags & F_LEAF)
  536.         fixedsize = (sizeof(DATUM) - sizeof(char));
  537.     else
  538.         fixedsize = (sizeof(IDATUM) - sizeof(char));
  539.  
  540.     save_key = (char *) NULL;
  541.  
  542.     /* move data */
  543.     for (i = 0; i < top; i++) {
  544.  
  545.         /*
  546.          *  Internal and leaf pages have different layouts for
  547.          *  data items, but in both cases the first entry in the
  548.          *  data item is a size_t.
  549.          */
  550.         d = (DATUM *) GETDATUM(h,i);
  551.         if (h->h_flags & F_LEAF) {
  552.             dsize = d->d_ksize + d->d_dsize + fixedsize;
  553.         } else {
  554.             dsize = d->d_ksize + fixedsize;
  555.         }
  556.  
  557.         /*
  558.          *  If a page contains duplicate keys, we have to be
  559.          *  careful about splits.  A sequence of duplicate keys
  560.          *  may not begin in the middle of one page and end in
  561.          *  the middle of another; it must begin on a page boundary,
  562.          *  in order for searches on the internal nodes to work
  563.          *  correctly.
  564.          */
  565.         if (where_h == left) {
  566.             if (save_key == (char *) NULL) {
  567.                 if (h->h_flags & F_LEAF) {
  568.                     if (d->d_flags & D_BIGKEY) {
  569.                         free_save = TRUE;
  570.                         bcopy(&(d->d_bytes[0]),
  571.                              (char *) &chain,
  572.                              sizeof(chain));
  573.                         if (_bt_getbig(t, chain,
  574.                                    &save_key,
  575.                                    &ignore)
  576.                             == RET_ERROR)
  577.                             return (RET_ERROR);
  578.                     } else {
  579.                         free_save = FALSE;
  580.                         save_key = (char *) &(d->d_bytes[0]);
  581.                     }
  582.                 } else {
  583.                     IDATUM *id = (IDATUM *) d;
  584.  
  585.                     if (id->i_flags & D_BIGKEY) {
  586.                         free_save = TRUE;
  587.                         bcopy(&(id->i_bytes[0]),
  588.                              (char *) &chain,
  589.                              sizeof(chain));
  590.                         if (_bt_getbig(t, chain,
  591.                                    &save_key,
  592.                                    &ignore)
  593.                             == RET_ERROR)
  594.                             return (RET_ERROR);
  595.                     } else {
  596.                         free_save = FALSE;
  597.                         save_key = (char *)
  598.                             &(id->i_bytes[0]);
  599.                     }
  600.                 }
  601.                 save_i = 0;
  602.                 save_lower = where_h->h_lower;
  603.                 save_upper = where_h->h_upper;
  604.             } else {
  605.                 if (_bt_cmp(t, save_key, i) != 0) {
  606.                     save_lower = where_h->h_lower;
  607.                     save_upper = where_h->h_upper;
  608.                     save_i = i;
  609.                 }
  610.                 if (h->h_flags & F_LEAF) {
  611.                     if (free_save)
  612.                         (void) free(save_key);
  613.                     if (d->d_flags & D_BIGKEY) {
  614.                         free_save = TRUE;
  615.                         bcopy(&(d->d_bytes[0]),
  616.                              (char *) &chain,
  617.                              sizeof(chain));
  618.                         if (_bt_getbig(t, chain,
  619.                                    &save_key,
  620.                                    &ignore)
  621.                             == RET_ERROR)
  622.                             return (RET_ERROR);
  623.                     } else {
  624.                         free_save = FALSE;
  625.                         save_key = (char *) &(d->d_bytes[0]);
  626.                     }
  627.                 } else {
  628.                     IDATUM *id = (IDATUM *) d;
  629.  
  630.                     if (id->i_flags & D_BIGKEY) {
  631.                         free_save = TRUE;
  632.                         bcopy(&(id->i_bytes[0]),
  633.                              (char *) &chain,
  634.                              sizeof(chain));
  635.                         if (_bt_getbig(t, chain,
  636.                                    &save_key,
  637.                                    &ignore)
  638.                             == RET_ERROR)
  639.                             return (RET_ERROR);
  640.                     } else {
  641.                         free_save = FALSE;
  642.                         save_key = (char *)
  643.                             &(id->i_bytes[0]);
  644.                     }
  645.                 }
  646.             }
  647.         }
  648.  
  649.         /* copy data and update page state */
  650.         where -= LONGALIGN(dsize);
  651.         (void) bcopy((char *) d, (char *) where, dsize);
  652.         where_h->h_upper = where_h->h_linp[where_i] =
  653.             (index_t) (where - (int) where_h);
  654.         where_h->h_lower += sizeof(index_t);
  655.         where_i++;
  656.  
  657.         /* if we've moved half, switch to the right-hand page */
  658.         nbytes -= LONGALIGN(dsize) + sizeof(index_t);
  659.         if ((freespc - nbytes) > nbytes) {
  660.             nbytes = 2 * freespc;
  661.  
  662.             /* identical keys go on the same page */
  663.             if (save_i > 0) {
  664.                 /* i gets incremented at loop bottom... */
  665.                 i = save_i - 1;
  666.                 where_h->h_lower = save_lower;
  667.                 where_h->h_upper = save_upper;
  668.             }
  669.             where = ((char *) right) + psize;
  670.             where_h = right;
  671.             switch_i = where_i;
  672.             where_i = 0;
  673.         }
  674.     }
  675.  
  676.     /*
  677.      *  If there was an active scan on the database, and we just
  678.      *  split the page that the cursor was on, we may need to
  679.      *  adjust the cursor to point to the same entry as before the
  680.      *  split.
  681.      */
  682.  
  683.     c = &(t->bt_cursor);
  684.     if ((t->bt_flags & BTF_SEQINIT)
  685.         && (c->c_pgno == h->h_pgno)
  686.         && (c->c_index >= switch_i)) {
  687.         c->c_pgno = where_h->h_pgno;
  688.         c->c_index -= where_i;
  689.     }
  690.     return (RET_SUCCESS);
  691. }
  692.